Video systems are known to include a plurality of communication devices and communication channels, which provide the communication medium for the communication devices. For example, the communication channel may be wireline connections or RF frequency carriers. To increase the efficiency of the video system, video that needs to be communicated is digitally compressed. The digital compression reduces the number of bits needed to represent the video while maintaining perceptual quality of the video. The reduction in bits allows more efficient use of channel bandwidth and reduces storage requirements. To achieve digital video compression, each communication device may include an encoder and a decoder. The encoder allows a communication device to compress video before transmission over a communication channel. The decoder enables the communication device to receive compressed video from a communication channel and render it visible. Communication devices that may use digital video compression include high definition television transmitters and receivers, cable television transmitters and receivers, video telephones, computers and portable radios.
Several standards for digital video compression have emerged, including International Telecommunications Union (ITU)-T Recommendation H.261, the International Standards Organization/International Electrotechnical Committee (ISO/IEC) 11172-2 International Standard (MPEG-1), and the forthcoming ISO/IEC 13818-2 standard (MPEG-2). These standards seek to efficiently represent a sequence of frames of video by exploiting the spatial and temporal redundancies in the video and by taking advantage of the perceptual qualities of the human eye. Temporal redundancy is exploited by estimating the motion in a sequence of frames.
Block matching algorithms are a known method for estimating motion within a video sequence. Each frame of the video sequence is divided into blocks of pixels. Block matching algorithms compare a current block that is to be encoded in one frame with blocks of the same size in a previous or future frame of the video sequence. If a matching block is found in a frame that has previously been encoded, then rather than encode the current block independently, the location of the matching block and any differences between the current block and the matching block may be encoded. Generally, encoding only the location and any difference information provides a more efficient method of encoding.
A full search block matching algorithm compares the current block that is to be encoded with all possible matches within a search region of a previously encoded frame. The search region is generally defined in terms of motion vectors (MV) that indicate a displacement in location from the upper leftmost pixel of the current block. For example, for a current block that has the upper leftmost pixel at an absolute location in Cartesian coordinates (x, y) of (10, 20), a search region of MV(.+-.5, .+-.5) has corner points at MV(-5, -5), MV(-5, +5), MV(+5, +5) and MV(+5, -5) and is defined by absolute locations (5, 15), (5, 25), (15, 25) and (15, 15) in the previously encoded frame. The full search algorithm always finds the best matching video block since it examines all choices in the search region. Therefore, the full search algorithm provides optimal video quality. The problem with the full search algorithm is that it is computation intensive. For example, for a search region of MV(.+-.48, .+-.31),6111 comparisons are necessary.
A hierarchical full search algorithm uses two search regions with different search point displacement patterns. The first region has a one pixel search point displacement pattern, i.e. comparison are made at intervals of one pixel. This search point displacement is the same as for the full search algorithm. The second region has a two pixel search point displacement pattern, i.e., comparison are made at every other pixel in both the horizontal and vertical directions. The first region is defined by MV(.+-.2, .+-.2) The second region is defined by MV(.+-.6, .+-.6) minus MV(.+-.2, .+-.2). The hierarchical full search algorithm reduces the number of comparisons over the full search algorithm and maintains adequate video quality, but is still quite computation intensive, especially for large search regions. Extending the hierarchical algorithm to cover a search region of MV(.+-.48, .+-.31) still requires approximately 1695 comparisons.
Another known block matching algorithm uses a very dense displacement pattern around MV(0, 0) and radially decreases the number of comparison points to cover a search region of approximately MV(.+-.10, .+-.10). The problem with this algorithm is that it is not readily extendible to larger search regions in the range of MV(.+-.48, .+-.31). Radially decreasing the number of search points causes the distance between comparison points and therefore, the location of comparison points to be highly irregular. This makes an implementation in hardware complex if not impossible. In addition, as the number of comparison points is reduced, the probability of finding a suitable match is substantially reduced. This causes inferior video quality.
The known block matching algorithms use a consistent search region and search displacement pattern without regard to the video sequence being encoded. This is problematic in that the search technique that is good for one sequence is not good for another sequence. For example, a video sequence, such as a car race that has fast motion, may require a large search region, but a sequence such as a talking head in a news cast, does not require a large search region.
Therefore, a need exists to restrict the search region and search technique to one that is reasonable in the computations required, but provides adequate video quality. Furthermore a need exists to be able to adapt the search technique to the video scene being encoded.